package noth.li.sort;


/**
 * 插入排序
 *
 * 1.从数组的第二个数据开始往前比较，即一开始用第二个数和他前面的一个比较，如果 符合条件（比前面的大或者小，自定义），则让他们交换位置。
 * 2.然后再用第三个数和第二个比较，符合则交换，但是此处还得继续往前比较，比如有 5个数8，15，20，45, 17,17比45小，需要交换，但是17也比20小，也要交换，当不需 要和15交换以后，说明也不需要和15前面的数据比较了，肯定不需要交换，因为前 面的数据都是有序的。
 * 3.重复步骤二，一直到数据全都排完。
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arr = {7, 5, 88, 6, 99, 55, 22, 35, 57, 89, 10, 999, 29, 762, 11, 22, 3, 45, 2, 2, 2, 2, 1, 3, 21, 1};

        //insertSortAsc(arr);
        insertSortDesc(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    /**
     * 插入排序 - 升序
     *
     * @param arr 要排序的数组
     */
    public static void insertSortAsc(int[] arr) {
        //默认第一个是有序的
        for (int i = 1; i < arr.length; i++) {
            //倒序开始匹配,如果当前数前面的一个数比他小,则互换
            //如果比他前一个还要大,则不用继续匹配,因为已经比有序数组的最大的还要大
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    arr[j] = arr[j] ^ arr[j - 1];
                    arr[j - 1] = arr[j] ^ arr[j - 1];
                    arr[j] = arr[j] ^ arr[j - 1];
                } else
                    break;
            }
        }
    }

    /**
     * 插入排序 - 降序
     *
     * @param arr 要排序的数组
     */
    public static void insertSortDesc(int[] arr) {
        //默认第一个是有序的
        for (int i = 1; i < arr.length; i++) {
            //倒序开始匹配,如果当前数前面的一个数比他大,则互换
            //如果比他前一个还要小,则不用继续匹配,因为已经比有序数组的最小的还要小
            for (int j = i; j > 0; j--) {
                if (arr[j] > arr[j - 1]) {
                    arr[j] = arr[j] ^ arr[j - 1];
                    arr[j - 1] = arr[j] ^ arr[j - 1];
                    arr[j] = arr[j] ^ arr[j - 1];
                } else
                    break;
            }
        }
    }
}
